package 剑指offer;

import java.math.BigInteger;

/**
 * Created by yang on 2016/8/24.
 *  一只青蛙一次可以跳上1级台阶，
 * 也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 */
public class FrogJumpStep {
    public int JumpFloor(int target) {

        if (target <= 3) {
            return target;
        }

        BigInteger count_step = BigInteger.ZERO;
        // 2级台阶一直加到不能再加
        // 对于每种情况排列组合
        int count_2 = 0;

        while(2 * count_2 <= target) {

            int count_1 = target - count_2 * 2;
            BigInteger num = factorial(count_1+count_2);
            BigInteger den = factorial(count_1).multiply(factorial(count_2));
            BigInteger temp = num.divide(den);
            count_step = count_step.add(temp);
            count_2++;
        }

        return count_step.intValue();
    }

    public BigInteger factorial(int num) {

        if(num <= 1) {
            return BigInteger.ONE;
        }else{
            return factorial(num-1).multiply(BigInteger.valueOf(num));
        }
    }

    public int fibonacci(int n){

        if(n <=1) {
            return n;
        }

        return fibonacci(n-1) + fibonacci(n-2);
    }
}
